Home > Search Results: keywords:"průnikové třídy grafů"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Algorithmic aspects of intersection-defined graph classes
 Jedličková, Nikola ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
Geometrically representable graphs are extensively studied area of research in contempo- rary literature due to their structural characterizations and efficient algorithms. The most frequently studied class of such graphs is the class of interval graphs. In this thesis we focus on two problems, generalizing the problem of recognition, for classes related to interval graphs. In the first part, we are concerned with adjusted interval graphs. This class has been studied as the right digraph analogue of interval graphs. For interval graphs, there are polynomial algorithms to extend a partial representation by given intervals into a full interval representation. We will introduce a similar problem - the partial ordering extension - and we will provide a polynomial algorithm to extend a partial ordering of adjusted interval digraphs. In the second part, we show two NP-completeness results regarding the simultaneous representation problem, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some k graphs can be represented so that every vertex is represented by the same object in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when k is a part of the input and graphs...
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English